package junior.贪心算法;

public class 多机调度 {
    static int[][] jobNode = {{ 2, 14, 4, 16, 6, 5, 3 },
                              { 1,  2, 3,  4, 5, 6, 7 }}; //jobNode[2][7]
    static String[] machineNode = {"m1","m2","m3"};
    public static void main(String[] args) {
        scheduling();
    }

    public static void scheduling(){
        quickSort(jobNode,0,jobNode[0].length-1);
        int len1 = jobNode[0].length;
        int len2 = machineNode.length;
        int[][] machine = new int[len2][2];
        int[][] schedule= new int[len2][len1];    // schedule[rowIndex][0] 记录每个工件的存放位置（=个数）
        for (int i = 0; i < len1; i++) {  // 最优子结构，最先空闲的机器，把最长的处理作业时间放入
            int rowIndex = firstBind(machine);
            int cloIndex = machine[rowIndex][1];
            schedule[rowIndex][cloIndex] = jobNode[1][i];

            machine[rowIndex][0] += jobNode[0][i];
            machine[rowIndex][1] += 1;
        }
        showJob();
        showSchedule(machine,schedule);
    }
    public static int firstBind(int[][] machine){ // 判断最先空闲机器
        int index = 0;
        int min = 100000;
        for (int i = 0; i < machine.length; i++) {
            if(machine[i][0] < min){
                min = machine[i][0];
                index = i;
            }
        }
        return index;
    }

    public static int[][] quickSort(int[][] array,int start, int end){
        int pivot = array[0][start];
        int i = start;
        int j = end;
        while (i<j) {
            while (i<j && array[0][j] < pivot)
                j--;
            while (i<j && array[0][i] > pivot)
                i++;
            if (i<j && array[0][i] == array[0][j]) {
                i++;
            } else {
                int temp1 = array[0][i],temp2 = array[1][i];
                array[0][i] = array[0][j]; array[1][i] = array[1][j];
                array[0][j] = temp1; array[1][j] = temp2;
            }
        }
        if (i-1 > start)
            array=quickSort(array,start,i-1);
        if (j+1 < end)
            array=quickSort(array,j+1,end);
        return array;
    }

    public static void showJob(){
        System.out.println("排序后的工件：");
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < jobNode[0].length; j++) {
                System.out.print(jobNode[i][j]+"\t");
            }
            System.out.println();
        }

    }
    public static void showSchedule(int[][] machine,int[][] schedule){
        System.out.println("工作量表：");
        System.out.println("工时\t\t工件数");
        for (int i = 0; i < machine.length; i++) {
            for (int j = 0; j < 2; j++) {
                System.out.print(machine[i][j]+"\t\t");
            }
            System.out.println();
        }
        System.out.println("\n"+"调度表：");
        for (int i = 0; i < machine.length; i++) { //jobNode.length / jobNode[0].length
            System.out.print(machineNode[i]+":\t");
            for (int j = 0; j < jobNode[0].length; j++) {
                System.out.print(schedule[i][j]+"\t");
            }
            System.out.println();
        }

    }
}
